A technique for embedding messages in digital image data is disclosed by Honsinger, et. al., (see “Method for Generating an Improved Carrier for use in an Image Data Embedding Application,” U.S. Pat. No. 6,044,156 issued Mar. 28, 2000). This method for embedding a hidden message includes the steps of forming a digitize version of the desired message; generating a random phase carrier; convolving the digitized version of the desired message and the random phase carrier to form a dispersed message; and combining the dispersed message with the digitized image to form an embedded hidden message image. Hidden messages may be embedded in photographic images recorded on film and paper using conventional photographic printing techniques, or they may be embedded in images produced on printers such as ink-jet and thermal dye transfer printers, by combining the dispersed image with a digital image processing techniques.
Hidden messages are recovered from the embedded hidden message image by cross correlating the embedded hidden message image containing the dispersed message with a decoding carrier to recover the embedded dispersed message; and extracting the digital image data for the recovered dispersed message.
One known techniques for extracting dispersed message when the image has been cropped and/or rotated employs a separate calibration signal contained in the image. Once the calibration signal was found, it is used to determine the dispersed message boundaries and the knowledge of the boundaries is used to extract the message from the image. Such a technique is described by Rhoads in U.S. Pat. No. 5,850,481, issued Dec. 15, 1998.
One problem with adding a calibration signal to an image is that it takes extra bandwidth that could be used for other purposes, such as storing more information in the hidden message. There is a need therefore for an improved method of identifying the dispersed message boundaries without the need for a separate calibration signal to aid in extraction of the dispersed message.
Honsinger, et. al., disclosed such a means (see U.S. patent application Ser. No. 09/453,160) to eliminate the requirement for a calibration signal. The method used by Honsinger is to build a message template used to indicate the location of the data in a message that is to be embedded in the image. The message template is represented as a rectangular array of pixel locations. Each pixel location of the template is either a one or a zero. If the pixel location contains a one, then the pixel location carries data for the hidden message. The message is encoded as a stream of binary bits, referred to as the original bit stream. The original bit stream, is first transformed to a stream of parity values, i.e., where the stream of bits are represented as +1 or −1, with the +1 representing a original bit value of 1 and a −1 representing an original bit value of 0. The pixel locations are then ordered in raster fashion to form a linear stream of data. Consequently, there are two data streams, the template data stream and the transformed original bit stream. It is convenient to consider the two streams as lists and for each list to have a pointer, referred to as the template pointer and the hidden message pointer. Both pointers are initially at the first elements of their respective lists. A hidden message data stream is formed as follows. The element of the template data stream pointed to by the template pointer is either a one or a zero. If it is a one, then the element pointed to by the hidden message pointer is entered into the hidden message stream and the hidden message pointer is advanced to the next element of the transformed original message stream. Other wise a zero is entered into the hidden message stream. In either case, the template pointer is advanced to the next template element.
The message template can have many possible configurations depending upon the number of pixels in the template and the number of bits in the original bit stream. If the template is an n×n pixel array and the original bit stream has m bits, then there are
         (                                        n            2                                                m                      )  possible configurations. It is not surprising that some configurations have better properties than others do. Consider the template array as torus, meaning that the top and bottom of the array and linked, as are the left and right sides of the array. Two desirable properties of the array are that the pixels with a one are isolated, and that a simple shift does not result in template pattern being replicated. The reason for the first property is to improve the resolution of the hidden message and the second is to assure the order of the hidden message is unambiguous.
Honsinger recognized that these are attractive properties and developed templates heuristically that had these characteristics. However, the method disclosed by Honsinger used a sequential means to attain the template and selected pixels based upon a predetermined template pattern, such as a spiral or a circle. Honsinger also mentions using a simulated annealing approach, but does not elaborate on the method. Two limitations arise from this approach, the first is number of potential templates considered is extremely restricted and the maximum number of bits permitted is determined arbitrarily.
Consequently, a need exists for overcoming the above-described drawbacks.